package com.yeung.exam;


import java.util.Scanner;

/**
 * dgbaechf in
 * gbdehfca post
 */
public class 携程重建二叉树 {
    public static void main(String[] args) {
//        char[] in = {'d', 'g', 'b', 'a', 'e', 'c', 'h', 'f',};//中序
//        char[] post = {'g', 'b', 'd', 'e', 'h', 'f', 'c', 'a'};//后续
        Scanner sc = new Scanner(System.in);
        String inLine = sc.nextLine();
        String postLine = sc.nextLine();
        if (inLine==null|| postLine==null) return;
        TreeNode treeNode = reConstructBinaryTree(inLine.toCharArray(), postLine.toCharArray());
        printPreOrder(treeNode);
    }

    /**
     * 建树
     */
    public static TreeNode reConstructBinaryTree(char[] in, char[] post) {
        if (post == null || in == null || post.length == 0 || in.length == 0 || post.length != in.length) {
            return null;
        }
        //二叉树的根节点
        TreeNode root = new TreeNode(post[post.length - 1]);
        root.left = null;
        root.right = null;

        //找到根节点在中序序列中的下标位置
        int leftNodeNums = 0;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == root.val) {
                break;
            }
            leftNodeNums++;
        }
        //找到左子树的后序遍历序列和中序遍历序列
        if (leftNodeNums > 0) {
            //左子树的后序序列
            char[] leftPostOrder = new char[leftNodeNums];
            //左子树的中序序列
            char[] leftInOrder = new char[leftNodeNums];
            for (int i = 0; i < leftNodeNums; i++) {
                leftPostOrder[i] = post[i];
                leftInOrder[i] = in[i];
            }

            //递归构建左子树
            TreeNode leftRoot = reConstructBinaryTree(leftInOrder, leftPostOrder);
            root.left = leftRoot;

        }

        //找到右子树的节点总数
        int rightNodeNum = in.length - 1 - leftNodeNums;
        if (rightNodeNum > 0) {
            //右子树的先序序列
            char[] rightPostOrder = new char[rightNodeNum];
            //右子树的中序序列
            char[] rightInOrder = new char[rightNodeNum];

            for (int i = 0; i < rightNodeNum; i++) {
                rightPostOrder[i] = post[leftNodeNums + i];
                rightInOrder[i] = in[leftNodeNums + 1 + i];
            }
            // 递归构建右子树
            TreeNode rightRoot = reConstructBinaryTree(rightInOrder, rightPostOrder); // 递归构建右子树
            root.right = rightRoot;
        }

        return root;
    }

    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode(char x) {
            val = x;
        }
    }

    /**
     * 先序遍历二叉树（递归实现）
     */
    public static void printPreOrder(TreeNode root) {
        if (root != null) {
            //完成左右子树遍历, 输出根节点值
            System.out.print(root.val);
            //遍历左子树
            printPreOrder(root.left);
            //遍历右子树
            printPreOrder(root.right);
        }
    }

}
